/************************************************************************/
/* MyList.h
/* Author: Wang, Changhai 
/* Created On: 5/2/2016
/* ADT of Two-Way Linked-List with head and tail node. 
/************************************************************************/
#ifndef MYLIST_H
#define  MYLIST_H
#include <iostream>
#include <cstdlib>
using namespace std;

template <typename Object>
class MyList
{
private:
	//Node data structure
	struct Node
	{
		Object data;
		Node *prev;
		Node *next;
		Node(const Object &d = Object(),Node *p=NULL, Node *n = NULL)
			:data(d),prev(p),next(n){}
	};

public: 
	//Const iterator sub-class
	class const_iterator
	{
	public:
		const_iterator() :current(NULL){}

		const Object& operator * () const
		{
			return retrive();
		}
		const_iterator& operator ++ ()
		{
			current = current->next;
			return *this;
		}

		const_iterator& operator++(int)
		{
			const_iterator old = *this;
			++(*this);
			return old;
		}

		bool operator == (const const_iterator &rhs) const
		{
			return current == rhs.current;
		}

		bool operator != (const const_iterator &rhs) const
		{
			return !(*this == rhs);
		}
	protected: 
		Node *current; 

		Object& retrive() const
		{
			return current->data;
		}

		//Constructor with Node as input is set as private so that client cannot use it. 
		const_iterator(Node *p) :current(p){}

		friend class MyList<Object>;// Make sure MyList can use the private member
	};

	//iterator sub-class, it inherit const_iterator to reuse the code. 
	class iterator : public const_iterator
	{
	public:
		iterator(){	}
		Object& operator *()
		{
			return retrive();
		}
		//If it is const, we reuse parent's implementation. 
		const Object& operator *() const
		{
			return const_iterator::operator *();
		}
		//++iterator  
		iterator operator++ ()
		{
			current = current->next;
			return *this;
		}
		//iterator++ 
		iterator operator ++(int)
		{
			iterator old = *this;
			++(*this);
			return old;
		}
	protected:
		iterator(Node *p) : const_iterator(p){}
		friend class MyList<Object>;
	};
public:
	//Constructor and destructor
	MyList()
	{
		init();
	}
	MyList(const MyList &rhs)
	{
		init();
		*this = rhs;
	}
	~MyList()
	{
		clear();
		delete head;
		delete tail;
	}

	//Necessary operator 
	const MyList& operator = (const MyList &rhs)
	{
		if (this == & rhs)
		{
			return *this;
		}
		clear();
		for(const_iterator itr = rhs.begin(); itr !=rhs.end(); ++itr)
			push_back(*itr);
		return *this;
	}
	//Iterator methods
	iterator begin()
	{
		return iterator(head->next);
	}
	const_iterator begin() const
	{
		return const_iterator(head->next);
	}
	iterator end()
	{
		return iterator(tail);
	}
	const_iterator end() const
	{
		return const_iterator(tail);
	}
	//Get object Info methods
	int size()const
	{
		return theSize;
	}
	bool empty() const
	{
		return size()==0;
	}

	Object & front()
	{
		return *begin();
	}
	const Object & front()const
	{
		return *begin();
	}
	Object &back()
	{
		return *--end();
	}
	const Object &back() const
	{
		return *--end();
	}

	//Object manipulation methods 
	//Delete all the items
	void clear()
	{
		while(!empty())
			pop_front();
	}
	
	void push_front(const Object & x)
	{
		insert(begin(),x);
	}
	void push_back(const Object &x)
	{
		insert(end(),x);
	}
	void pop_front()
	{
		erase(begin());
	}
	void pop_back()
	{
		erase(--end());
	}
	iterator insert(iterator itr, const Object &x);
	iterator  erase(iterator itr);
	iterator erase(iterator start, iterator end);
	
	
private:
	int theSize;
	Node *head;
	Node *tail;
	
	void init()
	{
		theSize = 0;
		head = new Node;
		tail = new Node;
		head->next =tail;
		tail->prev =head;
	}
};

//While create template object, it requires the function's definition to create a new class with the specific 
//type, so the best solution is put the declaration and defintion on same file so that client only need include on 
//file. 
template <typename Object>
typename MyList<Object>::iterator MyList<Object>::insert(typename MyList<Object>::iterator itr, const Object &x)
{
	Node *p = itr.current;
	theSize++;
	return iterator(p->prev = p->prev->next = new Node(x, p->prev, p));
}

template <typename Object>
typename MyList<Object>::iterator  MyList<Object>::erase(typename MyList<Object>::iterator itr)
{
	Node *p = itr.current;
	iterator retVal(p->next);
	p->prev->next = p->next;
	p->next->prev = p->prev;
	delete p ; 
	theSize--;
	return retVal;
}

template <typename Object>
typename MyList<Object>::iterator MyList<Object>::erase(typename MyList<Object>::iterator start, typename MyList<Object>::iterator end)
{
	for(iterator itr = start; itr != end; itr++)
		itr = erase(itr);
	return end;
}
#endif